    int dfs(TreeNode* root,bool right=true,int cur=0){
        if(!root)return cur-1;
        return max(dfs(root->left,false,right?cur+1:1),dfs(root->right,true,right?1:cur+1)); 
    }
    int longestZigZag(TreeNode* root) {
        return dfs(root);
    }

class Solution {
public:
    int _res=0;
    void dfs(TreeNode* root,bool right,int cur){
        if(!root)return ;
        _res=max(cur,_res);
        if(right)
        {
            dfs(root->left,false,cur+1);
            dfs(root->right,true,1);
        }
        else{
            dfs(root->right,true,cur+1);
            dfs(root->left,false,1);
        } 
    }
    int longestZigZag(TreeNode* root) {
        dfs(root,true,0);
        return _res;
    }
};